Problem statement: zenit14ckj

Okrem hrocha Karola potrebujú nudnú obhajobu znášať aj ostatní členovia komisie. Docentka pĺžica Lucia nemá rada osemsmerovky, ale nikdy nepohrdne partiou tradičnej hry menom námorná bitka.

Lucia sa práve chystá útočiť. Na súperkinom pláne zostáva ešte veľa nenapadnutých políčok a Lucia hľadá už len poslednú loď. Táto loď je podlhovastého tvaru s dĺžkou 3. Môže mať teda pri pohľade zhora dve podoby:

..........
.......#..
.###...#..
.......#..
..........

Lucia teraz rozmýšľa, ako najlepšie triafať, aby minimalizovala počet krokov, na ktorý určite hľadanú loď zasiahne. Nech bodka je políčko, na ktoré ešte nebolo útočené a X je políčko, ktoré už Lucia skúšala. Uvažujme nasledovnú situáciu:

..XX
..XX
....

Voľných políčok je ešte 8. V skutočnosti ale Lucii stačia dva pokusy:

..XX
..XX
LL..

Po výstrele na tieto dve políčka bude hľadaná loď určite zasiahnutá. Existujú aj iné možnosti výberu dvoch cieľov, ktoré splnia tento účel. Na druhej strane, pre každé nasmerovenie jediného výstrelu bude existovať možné umiestnenie lode také, že ju nezasiahneme.

Vstup a výstup

Na prvom riadku vstupu sú dve celé čísla \(R\) a \(S\) - rozmery bojového poľa. Tieto čísla sú aspoň 3 a najviac 10. Na každom z ďalších \(R\) riadkov je \(S\) znakov. Každý z týchto znakov je alebo bodka alebo X s významom ako v príklade vyššie. Môžete predpokladať, že vo vstupnej situácii existuje aspoň jedna oblasť voľných políčok, kde by sa mohla hľadaná loď nachádzať. Na výstup vypíšte jedno číslo: najmenší počet pokusov, ktoré pri vhodnom nasmerovaní garantujú zásah.

Ľahšia verzia

Vo vstupoch za aspoň 15 bodov sa nebudú vyskytovať znaky X. Ak si netrúfate na základnú verziu úlohy, môžete riešiť túto ľahšiu verziu.

Príklady

Input:

4 5
.....
.....
.....
.....

Output:

6

Vstupov bez X bude približne tretina.

Input:

5 6
...X..
...X.X
......
......
X.....

Output:

7

Input:

4 4
X..X
..X.
X...
..X.

Output:

2